﻿#include "SearchAlgorithm.h"
#include<Windows.h>
using namespace SearchAlgorithm;
using namespace std;

#pragma region Tools




#pragma endregion


#pragma region DFS

std::ostream& operator<<(std::ostream& out, const DFS::Pos& pos)
{
	out << "(" << pos.posx << "," << pos.posy << ")";
	return out;
}


SearchAlgorithm::DFS::DFS::DFS()
{
	GameMap = nullptr;
	Row = -1;
	Col = -1;
	Vis = nullptr;
	StartPos = { -1,-1 };
	EndPos = { -1,-1 };
	PathNumber = 0;
}

SearchAlgorithm::DFS::DFS::~DFS()
{
	if (Vis != nullptr)
	{
		for (int i = 0; i < Row; i++)
		{
			delete Vis[i];
			Vis[i] = nullptr;
		}
		delete[Row]Vis;


		Vis = nullptr;
		GameMap = nullptr;
		Row = -1;
		Col = -1;
		StartPos = { -1,-1 };
		EndPos = { -1,-1 };
		PathNumber = 0;
	}
}

void SearchAlgorithm::DFS::DFS::Init(int* map[], int row, int col, const Pos& StartPos, const Pos& EndPos)
{
	GameMap = map;
	Row = row;
	Col = col;
	PathNumber = 0;
	this->StartPos = StartPos;
	this->EndPos = EndPos;
	
	//初始化是否被访问过
	Vis = new bool* [Row];
	for (int i = 0; i < Row; i++)
	{
		Vis[i] = new bool[Col];
		//赋值初始化
		for (int j = 0; j < Col; j++)
		{
			Vis[i][j] = false;
		}
	}

}

void SearchAlgorithm::DFS::DFS::DisplayAllPath()
{
	for (const std::vector<Pos >& path : PathVec)
	{
		for (const Pos& pos : path)
		{
			std::cout << pos << "->";
		}
		cout << EndPos << endl;
	}
}

void SearchAlgorithm::DFS::DFS::DFSSearch(Pos pos)
{
	//终点
	if (pos == EndPos)
	{
		PathNumber++;
		//m_Path.push_back(EndPos);
		//将这一条路径存放起来
		PathVec.push_back(m_Path);
		return;
	}
	//标记已访问
	Vis[pos.posx][pos.posy] = true;
	//存放路径
	m_Path.push_back(pos);
	for (int i = 0; i < 4; i++)
	{
		Pos newPos = pos + Direct[i];
		//判断越界 && 未访问 && 可以走  
		if (in(newPos) && !Vis[newPos.posx][newPos.posy] && GameMap[newPos.posx][newPos.posy] == 0)
		{
			DFSSearch(newPos);
		}
	}

	//回溯  
	Vis[pos.posx][pos.posy] = false;
	m_Path.pop_back();
}
#pragma endregion


#pragma region BFS
std::ostream& operator<<(std::ostream& out, const BFS::Pos& pos)
{
	out << "(" << pos.posx << "," << pos.posy << ")";
	return out;
}

void SearchAlgorithm::BFS::BFS::Init(int* map[], int row, int col, const Pos& StartPos, const Pos& EndPos)
{
	GameMap = map;
	Row = row;
	Col = col;
	this->StartPos = new Pos(StartPos);
	this->EndPos = new Pos(EndPos);
	pathLen = 0;

	Inq = new bool* [Row];
	for (int i = 0; i < Row; i++)
	{
		Inq[i] = new bool[Col];
		//赋值初始化
		for (int j = 0; j < Col; j++)
		{
			Inq[i][j] = false;
		}
	}

}

void SearchAlgorithm::BFS::BFS::BFSFunc(Pos StartPos)
{
	BFSSearch(StartPos);
}

void SearchAlgorithm::BFS::BFS::DisplayAllPath()
{
	cout << "路径长度为：" << pathLen << endl;
	for (const Pos* pos : path)
	{
		std::cout << *pos << "->";
	}
}

BFS::BFS::BFS()
{
	GameMap = nullptr;
	Row = -1;
	Col = -1;
	Inq = nullptr;
	StartPos = nullptr;
	EndPos = nullptr;
	pathLen = 0;
}

BFS::BFS::~BFS()
{
	if (Inq != nullptr)
	{
		for (int i = 0; i < Row; i++)
		{
			delete Inq[i];
			Inq[i] = nullptr;
		}
		delete[Row]Inq;

		Inq = nullptr;
		GameMap = nullptr;
		Row = -1;
		Col = -1;
		if (StartPos != nullptr) delete StartPos;
		if (EndPos != nullptr) delete EndPos;
		StartPos = nullptr;
		EndPos = nullptr;
		pathLen = -1;
	}
}


void SearchAlgorithm::BFS::BFS::BFSSearch(Pos pos)
{
	//入口的父结点等于自己  
	//pos.parent = &pos;
	//起点入队 一开始是0步 
	m_Queue.push(new Pos(pos));
	//标记入队
	Inq[pos.posx][pos.posy] = true;

	//队列非空
	while (!m_Queue.empty())  
	{
		//取出队头
		Pos* nowPos = m_Queue.front();
		m_Queue.pop();
		//判断是否是终点
		if (*nowPos == *EndPos)
		{
			//pathLen = nowPos.step;
			//回溯到起点的终止条件是父结点等于nullptr
				//返回路径 向前回溯找到路径
			while (nullptr != nowPos)
			{
				path.push_front(nowPos);
				++pathLen;
				nowPos = nowPos->parent;
			}
			return;
		}
		//发散寻找队首的相邻点
		for (size_t i = 0; i < 4; i++)
		{
			Pos nextPos = *nowPos + Direct[i];
			//记录步骤  
			//nextPos.step = nowPos.step + 1;
			//没越界 没有入过栈 可以走
			if (in(nextPos) && !Inq[nextPos.posx][nextPos.posy] && GameMap[nextPos.posx][nextPos.posy] == 0)
			{
				//记录父结点  
				nextPos.parent = nowPos;
				//将下一步入队 标记
				m_Queue.push(new Pos(nextPos));
				Inq[nextPos.posx][nextPos.posy] = true;
			}
		}
	}
	//出现到这里就表示不会有这么一条路径
	pathLen = -1;
}

#pragma endregion


#pragma region AStart

/// <summary>
/// 初始化地图
/// </summary>
/// <param name="_maze">地图</param>
void SearchAlgorithm::Astar::AStar::Init(std::vector<std::vector<int>>& _maze)
{
	this->_maze = _maze;
}

/// <summary>
/// 获取路径  
/// </summary>
/// <param name="StartPos">起始点</param>
/// <param name="EndPos">结束点</param>
/// <param name="isIgnoreCorner">遇到障碍物时是否考虑斜边可走</param>
/// <returns>路径列表</returns>
std::forward_list<Astar::Point* > SearchAlgorithm::Astar::AStar::GetPath(Astar::Point& StartPos, Astar::Point& EndPos, bool isIgnoreCorner)
{
	//初始化一个路径存放容器  
	std::forward_list<Point* > path;
	//去查找路径 
	Point* result = FindPath(StartPos, EndPos, isIgnoreCorner);
	
	//返回路径 向前回溯找到路径
	while (nullptr != result) 
	{
		path.push_front(result);
		result = result->parent;
	}

	//清空临时开闭列表 防止重复使用GetPath导致的结果异常  
	openList.clear();
	closeList.clear();
	return path;
}


/// <summary>
/// A*算法的核心 查找路径
/// </summary>
/// <param name="StartPos">起始点</param>
/// <param name="EndPos">结束点</param>
/// <param name="isIgnoreCorner">遇到障碍物时是否考虑斜边可走</param>
/// <returns></returns>
Astar::Point* SearchAlgorithm::Astar::AStar::FindPath(Point& StartPos, Point& EndPos, bool isIgnoreCorner)
{
	//先将起始点加入到开启列表
	openList.push_back(new Point(StartPos.x, StartPos.y));
	do 
	{
		//在开启列表中去找F最小的点
		Point* curPoint = GetLeastFPoint();
		//从openList移入到CloseList中  
		openList.remove(curPoint);
		closeList.push_back(curPoint);

		//开始查找周围 条件是1.可走  2.没有在closeList中
		vector<Point* >surroundPoints = GetSurroundPoints(curPoint, isIgnoreCorner);
		for (Point* target : surroundPoints) 
		{
			if (!IsInList(openList, target))
			{
				//设置父结点
				target->parent = curPoint;
				//计算代价值
				target->G = CalcG(curPoint, target); //实际代价
				target->H = CalcH(target, &EndPos); //估计代价
				target->F = CalcF(target); //总代价
				openList.push_back(target); //加入到openList
			}
			//第二次查找 条件是是否在openList中 比较两者谁更优  
			//对于某一个格子，他在开始列表中，计算G值，如果比原来的大，就不需要走了。
			//否则设置他的父结点为当前点，并更新G和F
			else 
			{
				int tmpG = CalcG(curPoint, target);
				//重新计算
				if (tmpG < target->G) 
				{
					//更新父结点  
					target->parent = curPoint;
					//更新GF
					target->G = tmpG;
					target->F = CalcF(target);
				}
			}
			//查找结束点是否在开启列表中，如果在，那么一定有一条路径被找到了  
			Point* resPoint = IsInList(openList, &EndPos);
			if (nullptr != resPoint) 
			{
				return resPoint;
			}
		}
		//当所有可以走的点都走完了还没有找到，那就是没有了
	} while (!openList.empty());
	return nullptr;
}


/// <summary>
/// 找到开启列表中F最小的点
/// </summary>
/// <returns>开启列表中F最小的点的地址</returns>
Astar::Point* SearchAlgorithm::Astar::AStar::GetLeastFPoint()
{
	Point* curPoint = nullptr;
	//遍历整个打开列表 找到持有最小的F的点
	if(!openList.empty())
	{
		curPoint = openList.front();
		for ( Point*& point : openList) 
		{
			if (point->F < curPoint->F) 
			{
				curPoint = point;
			}
		}
	}
	return curPoint;
}

/// <summary>
/// 找到传入的当前点周围所有可走点
/// </summary>
/// <param name="point">当前点</param>
/// <param name="isIgnoreCorner">遇到障碍物时是否考虑斜边可走</param>
/// <returns>所有可走的点</returns>
vector<Astar::Point*> SearchAlgorithm::Astar::AStar::GetSurroundPoints(const Point* point, bool isIgnoreCorner) const
{
	//最多8个方位
	vector<Point* > surroundPoints;

	for (int x = point->x - 1; x <= point->x + 1; x++)
	{
		for (int y = point->y - 1; y <= point->y + 1; y++)
		{
			Point* target = new Point(x, y);
			if (IsCanReach(point, target, isIgnoreCorner))
			{
				surroundPoints.push_back(target);
			}
		}
	}
	return surroundPoints;
}
/// <summary>
/// 判断某个点是否可以走到Target点
/// </summary>
/// <param name="point">起点</param>
/// <param name="target">目标点</param>
/// <param name="isIgnoreCorner">遇到障碍物时是否考虑斜边可走</param>
/// <returns></returns>
bool SearchAlgorithm::Astar::AStar::IsCanReach(const Point* point, const Point* target, bool isIgnoreCorner) const
{
	//如果点与当前点重合、超出地图、不可行(障碍物)、在关闭列表  返回false
	if (target->x < 0 || target->x >= _maze.size() || target->y < 0 || target->y >= _maze[0].size() //xy超出范围
		|| _maze[target->x][target->y] == 1 || (target->x == point->x && target->y == point->y) //地图障碍物和相同点 
		|| IsInList(closeList, target) 
		) 
	{
		return false;
	}
	//判断是直线还是斜线  
	//直线
	if (abs(point->x - target->x) + abs(point->y - target->y) == 1) 
	{
		return true;
	}
	//斜线，需要确定能不能走 
	else 
	{
		//首先是没有遮挡物，可以走
		if (_maze[point->x][target->y] == 0 && _maze[target->x][point->y] == 0) 
		{
			return true;
		}
		else 
		{
			//自定义 可走还是不可走
			return isIgnoreCorner;
		}
	}
}

/// <summary>
/// 判断某个点是否在链表中
/// </summary>
/// <param name="list">探查链表</param>
/// <param name="point">待探查元素</param>
/// <returns>存在返回该点，否则返回nullptr</returns>
Astar::Point* SearchAlgorithm::Astar::AStar::IsInList(const std::list<Point*>& list, const Point* point) const
{
	//std::list<Point* >::const_iterator It = find(list.begin(), list.cend(), point);
	//if (list.cend() == It) 
	//{
	//	return nullptr;
	//}
	//return *It;
	for (Point* p : list) 
	{
		if (point->x == p->x && point->y == p->y) 
		{
			return p;
		}
	}
	return nullptr;

}

#pragma endregion

